
namespace AlgorithmShellSort {

    // show debug log
    const isDebug: boolean = true;

    // 希尔排序，步长用最简单的长度减半至1
    function shellSort(ary: number[]) {
        const len: number = ary ? ary.length : 0;
        if (len <= 1) return;
        if (isDebug)
            console.log(`数组长度${len}，排序前数组：\n`, JSON.stringify(ary));
        for (let gap: number = len >> 1; gap > 0; gap >>= 1) {
            if (isDebug)
                console.log(`\n设置步长为${gap}开始遍历\n`);
            // 插入排序思路，从下一个数值开始比较
            for (let i: number = gap; i < len; i++) {
                let tarPos = i - gap;   // 目标位置(从当前位置前一个开始，向前查找)
                const temp = ary[i];     // 当前数值(做替换准备)
                while (tarPos >= 0 && ary[tarPos] > temp) {
                    ary[tarPos + gap] = ary[tarPos];
                    tarPos -= gap;
                }
                // 指针停止，指针的下一个位置就是正确的序列位置
                ary[tarPos + gap] = temp;
                if (isDebug)
                    console.log(`从数组位置${i}开始搜索，目标元素位置为${tarPos + gap}，排序后数组：\n`, JSON.stringify(ary));
            }
        }
    };


    function main() {
        const ary: number[] = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
        shellSort(ary);
    }
    main();
}